package search;

import java.util.LinkedList;

import comment.Comment;

/**
 *create by tbj
 */
public class BinarySearchTree<Key extends Comparable<Key>,Value> {
	private Node root;
	private int count;
	private class Node{
		private Key key;
		private Value value;
		private Node left;
		private Node right;
		public Node(Key key,Value value){
			this.key=key;
			this.value=value;
			this.left=this.right=null;
		}
		public Node(Node node){
			this.key = node.key;
            this.value = node.value;
            this.left = node.left;
            this.right = node.right;
		}
		@Override
		public String toString() {
			return "Node [key=" + key + ", value=" + value + ", left=" + left + ", rigth=" + right + "]";
		}
	}
	public BinarySearchTree(){
		root=null;
		count=0;
	}
	public int Size(){
		return count;
	}
	public boolean isEmpty(){
		return count==0;
	}
	public void insert(Key key,Value value){
		root=_insert(root, key, value);
	}
	private Node _insert(Node node,Key key,Value value){
		if(node == null){
			count++;
			return new Node(key,value);
		}else if(key.compareTo(node.key) == 0){
			node.value=value;
		}else if(key.compareTo(node.key) < 0){
			node.left=_insert(node.left, key, value);
		}else{
			node.right=_insert(node.right, key, value);
		}
		return node;
	}
	public boolean contain(Key key){
		return _contain(root,key);
	}
	private boolean _contain(Node node,Key key){
		if(node == null){
			return false;
		}else if(key.compareTo(node.key) == 0){
			return true;
		}else if(key.compareTo(node.key) < 0){
			return _contain(node.left , key);
		}else{
			return _contain(node.right, key);
		}
	}
	public Value search(Key key){
		return _search(root,key);
	}
	private Value _search(Node node,Key key){
		if(node == null){
			return null;
		}else if(key.compareTo(node.key) == 0){
			return node.value;
		}else if(key.compareTo(node.key) < 0){
			return _search(node.left, key);
		}else{
			return _search(node.right, key);
		}
	}
	public void preOrder(){
		_preOrder(root);
	}
	private void _preOrder(Node node){
		if(node != null){
			System.out.print(node.key+" ");
			_preOrder(node.left);
			_preOrder(node.right);
		}
	}
	public void inOrder(){
		_inOrder(root);
	}
	private void _inOrder(Node node){
		if(node != null){
			_inOrder(node.left);
			System.out.print(node.key+" ");
			_inOrder(node.right);
		}
	}
	public void postOrder(){
		_postOrder(root);
	}
	private void _postOrder(Node node){
		if(node != null){
			_postOrder(node.left);
			_postOrder(node.right);
			System.out.print(node.key+" ");
		}
	}
	public void levelOrder(){
		LinkedList<Node> q=new LinkedList<>();
		q.add(root);
		while(!q.isEmpty()){
			Node node=q.remove();
			System.out.print(node.key+" ");
			if(node.left !=null){
				q.add(node.left);
			}
			if(node.right !=null){
				q.add(node.right);
			}
		}
	}
	public Key minimum(){
		if(count != 0){
			Node minNode=_minimum(root);
			return minNode.key;
		}
		return null;
	}
	private Node _minimum(Node node){
		if(node.left == null){
			return node;
		}
		return _minimum(node.left);
	}
	public Key maximum(){
		if(count != 0){
			Node maxNode=_maximum(root);
			return maxNode.key;
		}
		return null;
	}
	private Node _maximum(Node node){
		if(node.right == null){
			return node;
		}
		return _maximum(node.right);
	}
	public void removeMin(){
		if(root != null){
			root = _removeMin(root);
		}
	}
	private Node _removeMin(Node node){
		if(node.left == null){
			Node rightNode=node.right;
			node.right=null;
			count--;
			return rightNode;
		}
		node.left=_removeMin(node.left);
		return node;
	}
	public void removeMax(Node node){
		if(root!=null){
			root=_removeMax(root);
		}
	}
	private Node _removeMax(Node node){
		if(node.right==null){
			Node leftNode=node.left;
			node.left=null;
			count--;
			return leftNode;
		}
		node.right=_removeMax(node.right);
		return node;
	}
	public void remove(Key key){
		root=_remove(root,key);
	}
	private Node _remove(Node node,Key key){
		if(node == null){
			return null;
		}
		if(key.compareTo(node.key) < 0){
			node.left=_remove(node.left, key);
			return node;
		}else if(key.compareTo(node.key) > 0){
			node.right= _remove(node.right, key);
			return node;
		}else{
			if(node.left==null){
				Node rightNode=node.right;
				node.right=null;
				count--;
				return rightNode;
			}else if(node.right==null){
				Node leftNode=node.left;
				node.left=null;
				count--;
				return leftNode;
			}
			Node successor=new Node(_minimum(node.right));
			count++;
			
			successor.right=_removeMin(node.right);
			successor.left=node.left;
			
			node.left=node.right=null;
			count--;
			return successor;
		}
	}
	

	public static void main(String[] args) {
		/*int N = 20;
        // 创建一个数组，包含[0...N)的所有元素
        int[] arr = new int[N];
        for(int i = 0 ; i < N ; i ++)
            arr[i] = new Integer(i);
        // 打乱数组顺序
        for(int i = 0 ; i < N ; i ++){
            int pos = (int) (Math.random() * (i+1));
            Integer t = arr[pos];
            arr[pos] = arr[i];
            arr[i] = t;
        }*/
		int[] arr=Comment.getSortIntArr();
		BinarySearchTree<Integer, String> bst=new BinarySearchTree<>();
		for(int i=0;i<arr.length;i++){
			bst.insert(arr[i], String.valueOf(arr[i]));
		}
		System.out.println(bst.maximum());
	}
}
